package Algorithm.Offer;

//在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。
//请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
public class Offer03 {
    public static void main(String[] args) {
        int[][] arr = {{1, 2, 8, 9},
                {2, 4, 9, 12},
                {4, 7, 10, 13},
                {6, 8, 11, 15}};
        System.out.println(function01(14, arr));
        System.out.println(function02(10, arr));
    }

    //选取数组查找范围内的右上角的数字，如果该数字等于要查找的数字，则查找结束。
    //如果该数字小于要查找的数字，则剔除该数字所在的行；
    //如果该数字大于要查找的数字，则剔除该数字所在的列；
    public static boolean function01(int target, int[][] arr) {
        int rows = arr.length;
        int columns = arr[0].length;
        int row = 0;
        int column = columns - 1;

        while (column >= 0 && row < rows) {
            if (arr[row][column] == target) {
                return true;
            }
            if (arr[row][column] > target) {
                column--;
            } else {
                row++;
            }
        }
        return false;
    }

    //选取数组查找范围内的左下角的数字，如果该数字等于要查找的数字，则查找结束；
    //如果该数字小于要查找的数字，则剔除该数字所在的列；
    //如果该数字大于要查找的数字，则剔除该数字所在的行；
    public static boolean function02(int target, int[][] arr) {
        int rows = arr.length;
        int columns = arr[0].length;

        int row = rows - 1;
        int column = 0;

        while (row >= 0 && column < columns) {
            if (arr[row][column] == target) {
                return true;
            }
            if (arr[row][column] < target) {
                column++;
            } else {
                row--;
            }
        }
        return false;
    }
}
